/* 
 * trans.c - 矩阵转置 B = A^T
 *
 * 每个转置函数必须具有以下形式的原型：
 * void trans(int M, int N, int A[N][M], int B[M][N]);
 *
 * 转置函数的评估标准是：在块大小为 32 字节的 1KB 直接映射缓存上，计算缓存未命中的次数。
 */ 
#include <stdio.h>
#include "cachelab.h"

/*
 * is_transpose - 辅助函数，检查 B 是否是 A 的转置。
 * 可以在转置函数返回之前调用此函数来检查转置的正确性。
 */
int is_transpose(int M, int N, int A[N][M], int B[M][N]);

/* 
 * transpose_submit - 这是用于作业 Part B 评分的解决方案转置函数。
 * 不要更改描述字符串 "Transpose submission"，因为驱动程序会搜索此字符串来识别要评分的转置函数。
 */
char transpose_submit_desc[] = "Transpose submission";
void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
    // 循环变量
    int i, j, k, l; 
    // 临时变量，用于缓存行优化，减少缓存未命中
    int v0, v1, v2, v3, v4, v5, v6, v7; 

    // 针对 32x32 矩阵的优化
    // 采用 8x8 块大小，并使用 8 个局部变量一次性读取一行数据，再转置写入。
    // 这样可以充分利用缓存行，减少冲突未命中。
    if (M == 32 && N == 32)
    {
        // 局部变量用于存储 A 矩阵的一行数据
        int v1, v2, v3, v4, v5, v6, v7, v8;
        // 遍历 32x32 矩阵，每次处理 8x8 的块
        for (i = 0; i < 32; i += 8) 
            for(j = 0; j < 32; j += 8) 
                // 遍历当前 8x8 块的行
                for(k = i; k < (i + 8); ++k) 
                {
                    // 将 A 矩阵的当前行（8个元素）加载到局部变量中
                    v1 = A[k][j];
                    v2 = A[k][j+1];
                    v3 = A[k][j+2];
                    v4 = A[k][j+3];
                    v5 = A[k][j+4];
                    v6 = A[k][j+5];
                    v7 = A[k][j+6];
                    v8 = A[k][j+7];
                    // 将局部变量中的数据转置写入 B 矩阵的对应列
                    B[j][k] = v1;
                    B[j+1][k] = v2;
                    B[j+2][k] = v3;
                    B[j+3][k] = v4;
                    B[j+4][k] = v5;
                    B[j+5][k] = v6;
                    B[j+6][k] = v7;
                    B[j+7][k] = v8;
                }
    }
    // 针对 64x64 矩阵的优化
    // 采用 8x8 块大小，但由于 64x64 矩阵的特殊性（每行需要 8 个缓存行），
    // 直接使用 8x8 块会导致严重的冲突未命中。
    // 因此，这里将 8x8 的块进一步细分为 4x4 的子块进行处理，并利用临时变量进行数据交换。
    else if (M == 64 && N == 64)
    {
        // 局部循环变量
        int x, y;
        // 局部变量用于存储 A 矩阵的元素
        int x1, x2, x3, x4, x5, x6, x7, x8;
        // 遍历 64x64 矩阵，每次处理 8x8 的块
        for (i = 0; i < N; i += 8)
            for (j = 0; j < M; j += 8)
            {
                // 处理 8x8 块的左上 4x8 部分
                for (x = i; x < i + 4; ++x)
                {
                    // 读取 A 矩阵的 8 个元素
                    x1 = A[x][j]; x2 = A[x][j+1]; x3 = A[x][j+2]; x4 = A[x][j+3];
                    x5 = A[x][j+4]; x6 = A[x][j+5]; x7 = A[x][j+6]; x8 = A[x][j+7];
                    
                    // 将前 4 个元素转置写入 B 矩阵的对应位置
                    B[j][x] = x1; B[j+1][x] = x2; B[j+2][x] = x3; B[j+3][x] = x4;
                    // 将后 4 个元素转置写入 B 矩阵的对应位置（注意 B 矩阵的行偏移）
                    B[j][x+4] = x5; B[j+1][x+4] = x6; B[j+2][x+4] = x7; B[j+3][x+4] = x8;
                }
                // 处理 8x8 块的右下 4x8 部分
                for (y = j; y < j + 4; ++y)
                {
                    // 读取 A 矩阵的 4 个元素
                    x1 = A[i+4][y]; x2 = A[i+5][y]; x3 = A[i+6][y]; x4 = A[i+7][y];
                    // 读取 B 矩阵的 4 个元素（用于对角线处理）
                    x5 = B[y][i+4]; x6 = B[y][i+5]; x7 = B[y][i+6]; x8 = B[y][i+7];
                    
                    // 将 A 矩阵的元素转置写入 B 矩阵
                    B[y][i+4] = x1; B[y][i+5] = x2; B[y][i+6] = x3; B[y][i+7] = x4;
                    // 将之前从 B 矩阵读取的元素转置写入 B 矩阵的另一部分
                    B[y+4][i] = x5; B[y+4][i+1] = x6; B[y+4][i+2] = x7; B[y+4][i+3] = x8;
                }
                // 处理 8x8 块的右上 4x4 部分
                for (x = i + 4; x < i + 8; ++x)
                {
                    // 读取 A 矩阵的 4 个元素
                    x1 = A[x][j+4]; x2 = A[x][j+5]; x3 = A[x][j+6]; x4 = A[x][j+7];
                    // 将 A 矩阵的元素转置写入 B 矩阵
                    B[j+4][x] = x1; B[j+5][x] = x2; B[j+6][x] = x3; B[j+7][x] = x4;
                }
            }
    }
    // 针对 61x67 矩阵的优化
    // 对于非规则大小的矩阵，首先处理可以被 8 整除的部分，然后处理剩余的边缘部分。
    // 核心思想是利用 8 个临时变量进行块转置，减少缓存未命中。
    else if(M == 61 && N == 67)
    {
        // 局部变量用于存储 A 矩阵的一行数据
        int v1, v2, v3, v4, v5, v6, v7, v8;
        // 计算可以被 8 整除的最大行数和列数
        int n = N / 8 * 8; 
        int m = M / 8 * 8; 
        // 遍历可以被 8 整除的块
        for (j = 0; j < m; j += 8) 
            for (i = 0; i < n; ++i) 
            {
                // 将 A 矩阵的当前行（8个元素）加载到局部变量中
                v1 = A[i][j];
                v2 = A[i][j+1];
                v3 = A[i][j+2];
                v4 = A[i][j+3];
                v5 = A[i][j+4];
                v6 = A[i][j+5];
                v7 = A[i][j+6];
                v8 = A[i][j+7];
                
                // 将局部变量中的数据转置写入 B 矩阵的对应列
                B[j][i] = v1;
                B[j+1][i] = v2;
                B[j+2][i] = v3;
                B[j+3][i] = v4;
                B[j+4][i] = v5;
                B[j+5][i] = v6;
                B[j+6][i] = v7;
                B[j+7][i] = v8;
            }
        // 处理右下角的剩余部分
        for (i = n; i < N; ++i) 
            for (j = m; j < M; ++j) 
            {
                v1 = A[i][j];
                B[j][i] = v1;
            }
        // 处理右上角的剩余部分
        for (i = 0; i < N; ++i) 
            for (j = m; j < M; ++j) 
            {
                v1 = A[i][j];
                B[j][i] = v1;
            }
        // 处理左下角的剩余部分
        for (i = n; i < N; ++i) 
            for (j = 0; j < M; ++j) 
            {
                v1 = A[i][j];
                B[j][i] = v1;
            }
    }
    // 默认情况：对于其他尺寸的矩阵，使用通用的块转置方法
    else
    {
        // 定义块大小，通常选择为缓存行大小的倍数，且能使数据尽可能留在缓存中
        // 对于1KB直接映射缓存，块大小32字节（8个int），8x8的块是常见的选择
        int BLOCK_SIZE = 8;

        // 遍历矩阵的行块
        for (i = 0; i < N; i += BLOCK_SIZE) { // i从0开始，每次增加BLOCK_SIZE，直到N
            // 遍历矩阵的列块
            for (j = 0; j < M; j += BLOCK_SIZE) { // j从0开始，每次增加BLOCK_SIZE，直到M
                // 在当前块内进行转置
                // 遍历当前行块内的行
                for (k = i; k < i + BLOCK_SIZE && k < N; k++) { // k从当前行块的起始行i开始，直到i+BLOCK_SIZE或N
                    // 如果当前列块可以完整加载8个元素（即j到j+7都在M范围内）
                    if (j + 7 < M) {
                        // 将A[k]行中的8个元素加载到临时变量中
                        v0 = A[k][j];     // 加载A[k][j]
                        v1 = A[k][j+1];   // 加载A[k][j+1]
                        v2 = A[k][j+2];   // 加载A[k][j+2]
                        v3 = A[k][j+3];   // 加载A[k][j+3]
                        v4 = A[k][j+4];   // 加载A[k][j+4]
                        v5 = A[k][j+5];   // 加载A[k][j+5]
                        v6 = A[k][j+6];   // 加载A[k][j+6]
                        v7 = A[k][j+7];   // 加载A[k][j+7]

                        // 将临时变量写入B的对应列，实现转置
                        B[j][k] = v0;       // 写入B[j][k]
                        B[j+1][k] = v1;     // 写入B[j+1][k]
                        B[j+2][k] = v2;     // 写入B[j+2][k]
                        B[j+3][k] = v3;     // 写入B[j+3][k]
                        B[j+4][k] = v4;     // 写入B[j+4][k]
                        B[j+5][k] = v5;     // 写入B[j+5][k]
                        B[j+6][k] = v6;     // 写入B[j+6][k]
                        B[j+7][k] = v7;     // 写入B[j+7][k]
                    } else {
                        // 如果当前列块不足8个元素（边缘块），则直接进行逐元素转置
                        // 这种情况下，为了保证正确性，牺牲部分缓存性能
                        for (l = j; l < j + BLOCK_SIZE && l < M; l++) { // l从当前列块的起始列j开始，直到j+BLOCK_SIZE或M
                            B[l][k] = A[k][l]; // 执行转置操作
                        }
                    }
                }
            }
        }
    }
}

/* 
 * 您可以在下面定义其他转置函数。我们定义了一个简单的函数来帮助您入门。
 */ 

/* 
 * trans - 一个简单的基线转置函数，未针对缓存进行优化。
 */
char trans_desc[] = "Simple row-wise scan transpose";
void trans(int M, int N, int A[N][M], int B[M][N])
{
    int i, j, tmp;

    // 简单地逐元素进行转置，没有考虑缓存优化
    for (i = 0; i < N; i++) {
        for (j = 0; j < M; j++) {
            tmp = A[i][j];
            B[j][i] = tmp;
        }
    }    

}

/*
 * registerFunctions - 此函数将您的转置函数注册到驱动程序。
 * 在运行时，驱动程序将评估每个注册的函数并总结其性能。
 * 这是尝试不同转置策略的便捷方法。
 */
void registerFunctions()
{
    /* 注册您的解决方案函数 */
    registerTransFunction(transpose_submit, transpose_submit_desc); 

    /* 注册任何其他转置函数 */
    registerTransFunction(trans, trans_desc); 

}

/* 
 * is_transpose - 此辅助函数检查 B 是否是 A 的转置。
 * 您可以在转置函数返回之前调用它来检查转置的正确性。
 */
int is_transpose(int M, int N, int A[N][M], int B[M][N])
{
    int i, j;

    // 遍历矩阵元素，检查 A[i][j] 是否等于 B[j][i]
    for (i = 0; i < N; i++) {
        for (j = 0; j < M; ++j) {
            if (A[i][j] != B[j][i]) {
                return 0; // 如果不相等，则不是转置
            }
        }
    }
    return 1; // 所有元素都相等，是转置
}
